package Algorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessboard {
    private static int X;  //表示棋盘的列
    private static int Y;  //棋盘的行

    //创建一个数组，用来标记棋盘的各个位置是否被访问过
    private static boolean visited[];

    //使用一个属性，标记棋盘的所有位置都被访问，
    private static boolean finished; //如果为true代表成功

    public static void main(String[] args) {

        //测试
        X = 8;
        Y = 8;
        int row = 1;
        int column = 1;

        //创建棋盘
        int[][] chessboard = new int[X][Y];
        visited = new boolean[X * Y];  //初始值都是false;

        traversalChessboard(chessboard, row - 1, column - 1, 1);

        //输出棋盘的情况
        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println("\n");
        }
    }

    /**
     * 完成骑士周游问题
     * @param chessboard  棋盘
     * @param row 马当前的位置的行 从0开始
     * @param column  马当前的位置的列 从0开始
     * @param step  是第几步， 初始位置就是第1步
     */
    public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        visited[row * X + column] = true;  //马的当前位置,标记为以访问
        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> ps = next(new Point(column, row));

        //遍历这个ArrayList
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);  //去取出一个可以走的位置，下一个位置

            //判断该点是否已经访问过
            if (!visited[p.y * X + p.x]) {  //代表没有被访问过

                System.out.println(1);
                traversalChessboard(chessboard, p.y, p.x, step + 1);  //递归
            }
        }

        //判断是否走完
        if (step < X * Y && !finished) { //说明还没有完成
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
        } else {
            finished = true;
        }

    }


    /**
     * 根据当前位置(Point对象)，计算哪些位置还能够走（point），并且放入到集合中
     * @param curPoint
     * @return
     */
    public static ArrayList<Point> next(Point curPoint){

        //创建一个ArrayList
        ArrayList<Point> ps = new ArrayList<Point>();

        //创建一个point
        Point p1 = new Point();
        if((p1.x = curPoint.x -2) >= 0 && (p1.y = curPoint.y -1) >=0){ //代表没出棋盘
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x -2) >= 0 && (p1.y = curPoint.y +1) >=0){
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x -1) >= 0 && (p1.y = curPoint.y -2) >=0){
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x -1) >= 0 && (p1.y = curPoint.y +2) >=0){
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x +1) >= 0 && (p1.y = curPoint.y -2) >=0){
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x +1) >= 0 && (p1.y = curPoint.y +2) >=0){
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x +2) >= 0 && (p1.y = curPoint.y -1) >=0){
            ps.add(new Point(p1));
        }
        if((p1.x = curPoint.x +2) >= 0 && (p1.y = curPoint.y +1) >=0){
            ps.add(new Point(p1));
        }
        return ps;
    }

    //根据当前这一步所有的下一步的选择位置进行非递减排序
    public static void sort(ArrayList<Point> ps){

    }


}
